/*************************************************************************
> File Name: sort.h
> Author: icebear
> Mail: 3322366195@qq.com
> Created Time: 2023-07-23 21:17:28
> Description: 仿写Java的sort方法
************************************************************************/
#ifndef SORT_H
#define SORT_H
/**
 * arr 待排序数组
 * length 数组长度
 */
int sortArray(int arr[], int length);

static void swap(int *a, int *b);
static void insertionsort(int arr[], int begin, int end);
static void quickSort(int arr[], int begin, int end);
static int partition(int arr[], int bengin, int end);
static void merge(int arr[], int begin, int mid, int end);
static void mergeSort(int arr[], int begin, int end);

int sortArray(int arr[], int length)
{
    if (length < 47)
    {
        insertionsort(arr, 0, length);
    }
    else if (length < 286)
    {
        quickSort(arr, 0, length - 1);
    }
    else
    {
        mergeSort(arr, 0, length - 1);
    }
}
// 小于47时用插入排序
static void insertionsort(int arr[], int begin, int end)
{
    int i = 0, j = 0;
    int key = 0;
    for (i = begin; i < end; i++) // 1.从第二个开始、第一个数总是有序的
    {
        // 初始化
        key = arr[i];
        j = i - 1; // 从i-1开始判断是否移位
        // 调整位置
        while (j >= 0 && arr[j] > key) // 2.移动所有比他大的数，直到遇见一个小于等于他得数
        {
            arr[j + 1] = arr[j]; // 3.移动的(  j+1 =j  截止在j)
            j--;
        }
        // 赋值    将他放在j+1的位置
        arr[j + 1] = key; // 4.由于前j个元素有序
    }
}
// 47-286时用快速排序
static void quickSort(int arr[], int begin, int end)
{
    // 划分成两个部分
    if (begin < end)
    {
        int mid = partition(arr, begin, end);
        quickSort(arr, begin, mid - 1);
        quickSort(arr, mid + 1, end);
    }
}
static int partition(int arr[], int bengin, int end)
{
    int sign = arr[end];
    int i = bengin - 1; // begin-1开始
    for (int j = bengin; j < end; j++)
    {
        if (arr[j] <= sign) // 如果小于等于基准，交换到i+1和
        {
            swap(&arr[++i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[end]); // 将基准放置到下一个位置
    return i + 1;
}
// 大于286时用快速排序
static void mergeSort(int arr[], int begin, int end)
{
    if (begin < end)
    {
        int mid = begin + (end - begin) / 2;
        mergeSort(arr, begin, mid);   // 左递归
        mergeSort(arr, mid + 1, end); // 右递归
        merge(arr, begin, mid, end);  // 合并
    }
}

static void merge(int arr[], int begin, int mid, int end)
{
    //*******************初始化*******************
    int i = 0, j = 0, k = begin;
    int leftSize = mid - begin + 1;
    int rightSize = end - mid;
    int left[leftSize];
    int right[rightSize];
    for (i = 0; i < leftSize; i++)
    {
        left[i] = arr[begin + i];
    }
    for (i = 0; i < rightSize; i++)
    {
        right[i] = arr[mid + 1 + i];
    }
    i = 0;
    //*******************选择更小的插入原数组*******************
    while (i < leftSize && j < rightSize)
    {
        if (left[i] <= right[j])
        {
            arr[k++] = left[i++];
        }
        else
        {
            arr[k++] = right[j++];
        }
    }
    //*******************处理越界*******************
    while (i < leftSize)
    {
        arr[k++] = left[i++];
    }

    while (j < rightSize)
    {
        arr[k++] = right[j++];
    }
}

static void swap(int *a, int *b)
{
    if (a != b)
    {
        *a = *a ^ *b;
        *b = *a ^ *b;
        *a = *a ^ *b;
    }
}

#endif
